#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
void Swap(int* p1, int* p2)
{
	int* tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;

}
void AdjustDown(int* a,int n,int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child ++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}
void HeapSort(int* p, int n)
{
	int i = ((n - 1) - 1) / 2;
	for (i; i > 0; i--)
	{
		AdjustDown(p, n, i);
	}
	int end = n - 1;
	while (end)
	{
		Swap(&p[0], &p[end]);
		AdjustDown(p, end, 0);
		end--;
	}
}

void test1()
{
	int arr[] = { 3,9,6,8,10 };
	int n = sizeof(arr) / sizeof(int);
	HeapSort(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}

void PrintTopK(const char* filename,int n)
{	//建堆
	FILE* fout = fopen(filename,"r");
	if (fout==NULL)
	{
		perror("fopen error");
		exit(-1);
	}
	int* minheap = (int*)malloc(sizeof(int) * n);
	if (minheap == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	for (int i = 0; i < n; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
	//前n个小堆
	for (int i = (n - 2) * 2; i >= 0; i--)
	{
		AdjustDown(minheap, n, i);
	}
	//minheap[0]为前n个最小，比它大的入堆
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, n, 0);
		}
	}
	//int end = n-1;
	//while (end)
	//{
	//	Swap(&minheap[0], &minheap[end]);
	//	AdjustDown(minheap, end, 0);
	//	end--;
	//}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");

	free(minheap);
	fclose(fout);
}

void CreatData()
{
	int n = 1000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	fprintf(fin, "%d\n", 1000005);
	fprintf(fin, "%d\n", 10000045);
	fprintf(fin, "%d\n", 1000001);
	fprintf(fin, "%d\n", 1000006);
	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 100000;
		fprintf(fin, "%d\n", x);
	}




	fclose(fin);
}
//int main()
//{
//	test1();
//	//CreatData();
//	//PrintTopK("data.txt",5);
//	return 0;
//}

//单值二叉树
//bool isUnivalTree(struct TreeNode* root) {
//	if (root == NULL)
//		return true;
//	if (root->left && root->left->val != root->val)
//		return false;
//	if (root->right && root->right->val != root->val)
//		return false;
//	return isUnivalTree(root->left) && isUnivalTree(root->right);
//}

//二叉树的最大深度
//int maxDepth(struct TreeNode* root) {
//	if (root == NULL)
//		return 0;
//	//保存返回值    
//	int left = maxDepth(root->left);
//	int right = maxDepth(root->right);
//
//	return right > left ? right + 1 : left + 1;
//}